PJW hash function
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
PJW hash function is a non-cryptographic hash function created by Peter J. Weinberger of AT&T Bell Labs.
Contents
• See also
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Other versions
A variant of PJW hash had been used to create ElfHash or Elf64 hash that is used in Unix object files with ELF format.
Allen Holub has created a portable version of PJW hash algorithm that had a bug and ended up in several textbooks, as the author of one of these textbooks later admitted.cite-ref-1[1]
Algorithm
PJW hash algorithm involves shifting the previous hash and adding the current byte followed by moving the high bits:cite-ref-2[2]
algorithm PJW_hash(s) is
uint h := 0
bits := uint size in bits
for i := 1 to |S| do
h := h << bits/8 + s[i]
high := get top bits/8 bits of h from left
if high ≠ 0 then
h := h xor (high >> bits * 3/4)
h := h & ~high
return h
Implementation
Below is the algorithm implementation used in Unix ELF format:cite-ref-3[3]
unsigned long ElfHash(const unsigned char *s)
{
unsigned long h = 0, high;
while (*s)
{
h = (h << 4) + *s++;
if (high = h & 0xF0000000)
h ^= high >> 24;
h &= ~high;
}
return h;
}
See also
References
cite-note-11. ↑ citerefbinstock1996Binstock, Andrew (1996). "Hashing Rehashed". Dr. Dobb's.
cite-note-22. ↑ "Hash Functions". www.cs.hmc.edu. Retrieved 2015-06-10.
cite-note-44. ↑ "ELF hash function may overflow". 12 April 2023. Retrieved 2023-04-14.